package com.java.comprehensive.arithmetic;

import cn.hutool.core.util.ArrayUtil;

public class KMP {


    public static void getNext(int[] next, String s) {
        //初始化
        //指向前缀末尾位置
        int j = 0;
        for (int i = 1; i < s.length(); i++) {
            //处理前后缀不相同
            while (j - 1 >= 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            //处理前后缀相同
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            //更新next
            next[i] = j;
        }
    }


    public static void getNextTwo(int[] next, String s) {

    }

    public static void main(String[] args) {
        String s = "aabaaf";
        int[] next = new int[s.length()];
        getNext(next, s);
        System.out.println(ArrayUtil.toString(next));
    }
}
